\documentclass[a4paper,12pt]{article} 
\usepackage[russian]{babel}
 \usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\begin{document}
 \section{Question 1}

{\bf 1.} 
$f(n) = f (n/2)+ 2 f (n/4) +  \Theta (n)$$

Assume that $n = 2^k$. Then this equation will be
$$f(2^k ) =f (2^{ k-1} )+ 2 f (2^{ k-2} ) +  \Theta (2^k)$$

Substitute $g(k)=f(2^k ) $:
$$g(k) = g(k-1) + 2 g(k-2) + \Theta (2^k)$$

Let's find a solution for homogeneous part
$$g(k) = g(k-1) + 2 g(k-2)$$

We try to define a solution in a form $c a^k$

$$c a^k = c a ^{k-1} + 2 c a^{k-2}$$

Dividing this equation on $c \not= 0$ and $a ^ {k-2} \not = 0$ we get

$$a^2 = a + 2 $$

which has roots $r_1 =2$ and $r_2 = -1$

So solution of homogeneous part is $c_1 2^k + c_2 (-1)^k$.

The driving function has the form $C 2^k$, that is it has the same form as one of solutions of homogeneous part. So the solution for inhomogeneous part should be in the form $P(k) 2^k$ where the degree of polynom $P$ should be increased on $1$ compared to the initial degree of polynom in driving function ($0$).

So the solution for ingomogeneous part has the form $(Ak + B) 2^k$.
Then the solution of initial equation $g(k)$ has the form $c_1 2^k + c_2 (-1)^k + c_3 k 2^k$, that is $g(k)$ is $\Theta(k 2^k)$.

Then subtituting $k = \log_2 n$ we get that $f(n)$ is $\Theta(n \log n)$.


{\bf 2.} 

$$f(n) = f (n -1) f (n - 2)$$
with $f(1) = 1$ and $f(2) = 2$

Let's take a logarithm of the equation:

$$\log_2 {f(n)} = \log_2 {f (n -1)} + \log_2 { f (n - 2)}$$

Substitute $g(n)=\log_2 {f(n + 1)}$:
$$g(n) = g(n-1) + g(n-2)$$

$g(0) = \log_2 f (1) = \log_2 1 = 0$

$g(1) = \log_2 f (2) = \log_2 2 = 1$

The characteristic equation in this case is
$$a^2 = a + 1$$

which has roots $r_1,r_2 = \frac {1 \pm \sqrt {5}}2$

So solution of homogeneous part is $c_1 ( \frac {1 + \sqrt {5}}2)^n + c_2 ( \frac {1 - \sqrt {5}}2)^n$.

Find $c_1$ and $c_2$ from initial constraints:

$g(0) = c_1 + c_2 = 0$

$g(1) = c_1 \frac {1 + \sqrt {5}}2 + c_2  \frac {1 - \sqrt {5}}2 = 1 $

\par{\bigskip}

$c_1 = - c_2$

$c_1 - c_2 = \frac 2 {\sqrt{5}}$

\par{\bigskip}

$c_1 = \frac 1 {\sqrt{5}} $

$c_2 = - \frac 1 {\sqrt{5}} $

\par{\bigskip}

So $g(n) =\log_2 {f(n + 1)}= \frac 1 {\sqrt{5}}  ( \frac {1 + \sqrt {5}}2)^n - \frac 1 {\sqrt{5}}  ( \frac {1 - \sqrt {5}}2)^n$

$f(n) = 2^{\left( \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1} - \frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}\right)}$

or $f(n) = 2^{ \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1}}2^ {-\frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}}$

Because $\exists C \; \forall n \; 2^ {-\frac 1 {\sqrt{5}}  \left( \frac {1 - \sqrt {5}}2\right)^{n-1}} < C $, then 
$f(n)$ is $\Theta\left(  2^{ \frac 1 {\sqrt{5}} \left( \frac {1 + \sqrt {5}}2\right)^{n-1}} \right)$
\section{Question 4}

Define $f(n)$ as the number of multiplications needed to compute the multiplication for length-n binary vectors.
Then from the definition of this multiplication $f(n)$ satistfies the following recurrency equation:

$$f(n) = 4 f (n/2) + \Theta (1)$$

Assume that $n = 2^k$. Then this equation will be

$$f(2^k ) = 4 f (2^{ k-1} )+ \Theta (1)$$

Substitute $g(k)=f(2^k ) $:

$$g(k) = 4 g(k-1) + \Theta (1)$$

This equation has solution $g(k) =  \Theta (4 ^k)$ via Master Theorem.

Subtituting $k = \log_2 n$ we get $f(n) =  \Theta (n^2)$.

\par{\bigskip}

This approach can be impoved using equation $$ab + cd = (a+c)(b+d) - cb - ad$$ that take place for defined multiplication of n-length vectors.

\begin{equation*}
\begin{split}
XY &= 2^n X_L Y_L + 2^{n/2} (X_L Y_R + X_R Y_L) + X_R Y_R =\\  
     &=2^n X_L Y_L + 2^{n/2} ((X_L + X_R)(Y_R + Y_L) - X_R Y_R - X_L Y_L) + X_R Y_R =\\
     &=(2^n - 2^{n/2} )X_L Y_L + 2^{n/2} ((X_L + X_R)(Y_R + Y_L)) + (1 -  2^{n/2} ) X_R Y_R
\end{split}
\end{equation*}

The number of multiplications in this case will follow this recurrency equation:
$$f(n) = 3 f (n/2) + \Theta (1)$$

The solution is $f(n) = \Theta (n^{\log_2 3})$ as it was deduced in the question 3.

\end{document}